#include <vector>
#include <map>
#include <algorithm>
#include "prime.h"

#if 0
void find_primes_below(int n, std::vector<int> &primes)
{
	primes.resize(0);

	if (n > 2)
		primes.push_back(2);

	for (int k = 3; k < n; k += 2)
	{
		// test whether k is a prime number.
		bool is_prime = true;
		for (int i = 1; i < (int)primes.size(); i++)
		{
			int p = primes[i];
			div_t d = div(k, p);
			if (d.rem == 0)
			{
				is_prime = false;
				break;
			}
			if (d.quot < p)
				break;
		}
		// add the number to prime list if it's a prime number.
		if (is_prime)
			primes.push_back(k);
	}
}
#else
void find_primes_below(int N, std::vector<int> &primes)
{
	primes.resize(0);
	prime_numbers p(N-1);
	for (prime_numbers::const_iterator it = p.cbegin(); it != p.cend(); ++it)
	{
		primes.push_back(*it);
	}
}
#endif

void prime_factorize(int n, std::vector<int> &primes)
{
	primes.resize(0);
	if (n <= 1)
		return;
	
	// divide by 2
	while (n % 2 == 0)
	{
		n >>= 1;
		primes.push_back(2);
	}

	// divide by odd number until sqrt(n)
	int p = 3;
	while (n > 1)
	{
		div_t d = div(n, p);
		if (d.rem == 0)
		{
			n = d.quot;
			primes.push_back(p);
		}
		else
		{
			if (d.quot < p)
			{
				primes.push_back(n);
				break;
			}
			p += 2;
		}
	}
}

void count_prime_factors(const std::vector<int> &primes, std::map<int, int> &map)
{
	map.clear();
	std::for_each(primes.cbegin(), primes.cend(), [&map](int p) {
		++map[p];
	});
}

bool is_prime(int n, const std::vector<int> &primes)
{
	if (n <= 1)
		return false;
	if (n == 2)
		return true;
	if (n % 2 == 0)
		return false;

	// test the primeness in the pre-built table
	int max_prebuilt = *primes.crbegin();
	if (n <= max_prebuilt)
	{
		return std::binary_search(primes.cbegin(), primes.cend(), n);
	}

	// If the number to test is beyond the pre-built table, check against
	// each prime first.
	for (auto it = primes.cbegin(); it != primes.cend(); ++it)
	{
		int p = *it;
		div_t d = div(n, p);
		if (d.rem == 0)
			return false;
		if (d.quot < p)
			return true;
	}
	
	// If the number is greater than max_prebuilt^2, we need to test
	// each odd number beyond max_prebuilt.
	for (int p = (max_prebuilt + 1) | 1; ; p += 2)
	{
		div_t d = div(n, p);
		if (d.rem == 0)
			return false;
		if (d.quot < p)
			return true;
	}
}

bool is_prime(int n)
{
	if (n <= 1)
		return false;
	if (n <= 3)
		return true;
	if (n % 2 == 0)
		return false;
	
	// If the number is greater than max_prebuilt^2, we need to test
	// each odd number beyond max_prebuilt.
	for (int p = 3; ; p += 2)
	{
		div_t d = div(n, p);
		if (d.rem == 0)
			return false;
		if (d.quot < p)
			return true;
	}
}

void totient(std::vector<int> &phi)
{
	int N = (int)phi.size() - 1;
	for (int n = 0; n <= N; n++)
	{
		phi[n] = (n % 2 == 0)? n / 2 : n;
	}
	for (int p = 3; p <= N; p += 2)
	{
		if (phi[p] == p)
		{
			for (int k = p; k <= N; k += p)
				phi[k] = phi[k] / p * (p - 1);
		}
	}
}

int totient(int n)
{
	int ret = n;
	prime_factorize_distinct(n, [&ret](int p, int k) {
		ret = ret / p * (p - 1);
	});
	return ret;
}
